//
//  schedule.cxx
//  Schedule
//
//  Created by Julius Canute on 2/15/12.
//  Copyright 2012 ABB. All rights reserved.
//
#include <string.h>
#include "schedule.h"
#define LIMIT 100000
#define MILLITOMICRO(x) x*1000 
#define MILLITONANO(x) x*1000000
#define MICROTONANO(x) x*1000
//This should return start time.
string mintime(string unit1, string unit2){
    string units;
    if (unit1 == unit2) {
        return unit1;
    }
    else
    {
        if ( unit1 == "ns" || unit2 == "ns" ) 
            return "ns";
        if ( unit1 == "us" || unit2 == "us" )
            return "us";
            
            }
    return "ms";
}

bool compare_items (const sequence &i,const sequence &j) { 
	
	return i.start_time < j.start_time;
	
}

int compute_lcm(bool *numbers, vector<int> &nums,int sz){
    
    
    int i=2,factors=1;
    while (i<=sz) {
        if (numbers[i]) {
            bool flag = false;
            for (int x=0; x<nums.size(); x++) {
                if (nums[x]%i==0) {
                    flag = true;
                    nums[x] = nums[x]/i;
                }
            }
            if (flag) 
                factors = factors*i;
            else
                i++;
            
        }
        else
            i++;
    }
    return factors;
    
}
int generate_prime(int n, bool *numbers)
{
    for (int i=2; i<=n; i++) 
        numbers[i] = true;
    
    
    for (int i=2; i<=n/2; i++) {
        if (numbers[i]) {
            for (int j=i+i; j<=n; j+=i) {
                numbers[j] =false;
            }
        }
    }
    return 0;
}
int check_overlap(vector < vector<int> > &m, vector <application> &apps, search_space &nn,int i, int j,int app_no,int ex_time,int s_time){
    if( !(nn.a[app_no]>=apps[app_no].order.size()) )
    {
        
        
        sequence s(app_no,nn.a[app_no]);
        s.start_time = s_time;
        bool flag = true,state = false;
        
        
        int a_ex_time;
        bool check = false;
        for(size_t k=1;k<nn.p[i].assign.size();k++)
        {
        	if(nn.p[i].assign[k].start_time<=s.start_time)
        		continue;
        	
        	
        	if (nn.p[i].assign[k-1].app_no < 0 || nn.p[i].assign[k-1].comp_no < 0)
                a_ex_time = 0;
            else
                a_ex_time = apps[nn.p[i].assign[k-1].app_no].order[nn.p[i].assign[k-1].comp_no].ex_time;
            
        	
        	int comp1 = nn.p[i].assign[k-1].start_time + a_ex_time;
        	int comp2 = nn.p[i].assign[k].start_time;
        	
        	if(comp1 < s.start_time)
        		comp1 = s.start_time;
            

            
        	if(comp2 - comp1 >= ex_time)
        	{
        		s.start_time = comp1;
        		check = true;
        		break;
        	}
        	
        	
        }
        
        if(!check)
        	s.start_time = -1;
        
        return s.start_time;
        
    }
    return -1;
}
int normalize_units(string min_unit,string actual_unit,int time){
    
    if (min_unit == "us")
        return MILLITOMICRO(time);
        
    
    if (min_unit == "ns")
    {
        if (actual_unit == "us") 
            return MICROTONANO(time);
        if (actual_unit == "ms")
            return MILLITONANO(time);
            
    }
    
    return time;
    
}
int process_node(vector <node*> &n,vector < vector<int> > &m,vector <application> &apps,queue <search_space> &q,search_space &s,int &a_sum){
    bool numbers[LIMIT];
    
    string min_unit = "ms";
    int m_ctime = 0;
    size_t m_comps = 0;
    int lcm;
    vector<int> ctime;
    ////Figure out the base timing unit
    for (int i=0; i<apps.size(); i++)
    {
        //m_ctime = max(apps[i].cycle_time,m_ctime);
        //m_comps = max(apps[i].order.size(),m_comps);
        min_unit = mintime(min_unit,apps[i].unit);
        //ctime.push_back(apps[i].cycle_time);
    }
    
    
    for (int i=0; i<s.p.size(); i++) {
        min_unit = mintime(min_unit,s.p[i].unit);
    }
    
    
    cout<<"Base Timing Unit:"<<min_unit<<endl;
    ////Figure out the base timing unit
    
    
    ////Coversion from one timing unit to another

    for (int i=0; i<apps.size(); i++)
    {
        if (apps[i].unit == min_unit)
            continue;
        
        for (int j=0; j<apps[i].order.size(); j++) 
            apps[i].order[j].ex_time = normalize_units(min_unit,apps[i].unit,apps[i].order[j].ex_time);
        
        
        apps[i].cycle_time = normalize_units(min_unit,apps[i].unit,apps[i].cycle_time);
        apps[i].unit = min_unit;
        
    }
    
    for (int i=0; i<s.p.size(); i++) {
        if(s.p[i].unit == min_unit)
            continue;
        
        s.p[i].left_capacity = normalize_units(min_unit,s.p[i].unit,s.p[i].left_capacity);
        
        s.p[i].unit = min_unit;
    
    }
    
    ////Coversion from one timing unit to another
    
    
    for (int i=0; i<apps.size(); i++)
    {
        m_ctime = max(apps[i].cycle_time,m_ctime);
        m_comps = max(apps[i].order.size(),m_comps);
        ctime.push_back(apps[i].cycle_time);
    }
    
    generate_prime(m_ctime, numbers);
    lcm = compute_lcm(numbers,ctime,m_ctime);
    cout<<"LCM:"<<lcm<<endl;
	
    
    
    for (size_t i=0; i<s.p.size(); i++) {
        int h_cycle_time = s.p[i].left_capacity;
        cout<<"Cycle time for host:"<<h_cycle_time<<endl;
        for (size_t j=0,h_stime=0; j <= ( lcm / h_cycle_time ); j++) {
            sequence s1(-1,-1);
            s1.start_time = h_stime;
            s.p[i].add_assignment_obj(s1);
            h_stime += h_cycle_time;
            //cout<<"Added object"<<endl;
            
        }
    }
    
    q.push(s);
    bool note[apps.size()][m_comps];
	while(!q.empty())
	{
        memset(note, false, sizeof(note[0][0]) * apps.size() * m_comps);
		search_space nn = q.front();
		q.pop();
		int sum = 0;
		for(size_t i=0;i<nn.p.size();i++)
		{
			//sum += nn.p[i].assign.size();
            for (size_t j=0;j<nn.p[i].assign.size() ;j++) {
                int a_no,c_no;
                a_no = nn.p[i].assign[j].app_no;
                c_no = nn.p[i].assign[j].comp_no;
                if(a_no!=-1 && c_no!=-1)
                {
                	if (!note[a_no][c_no])
                	{
                    	sum++;
                    	note[a_no][c_no] = true;
                	}
                }
                
            }
            
		}
		//cout<<"-"<<m[0].size()<<"-"<<m[1].size()<<"+"<<endl;
        //cout<<"(SUM):"<<sum<<" "<<"(ASUM):"<<a_sum<<endl;
		//cout<<"---------------------------------------------"<<endl;
		//nn.print_node(apps);
        
		if(sum == a_sum)
        {
            cout<<"Schedule Found..."<<endl;
            nn.print_search_node(apps);
            break;
        }
		for(size_t i=0;i<nn.p.size();i++)
		{
            
			for(size_t j=0;j<m[i].size();j++)
			{
                
                
                
                int app_no = m[i].at(j);
                int ex_time = apps[app_no].order[nn.a[app_no]].ex_time;
                int c_time = apps[app_no].cycle_time;
                //s.start_time = nn.est[app_no];
                
                sequence s(app_no,nn.a[app_no]);
                s.start_time = nn.est[app_no];
                
				s.start_time =  check_overlap(m,apps,nn,i,j,app_no,ex_time,nn.est[app_no]);
                //cout<<"AppNo:"<<s.app_no<<" CompNo:"<<s.comp_no<<" StartTime:"<<s.start_time<<" Assigned to processor("<<i<<")"<<endl;

                //cout<<"Getting:"<<s.start_time<<endl;
				if(s.start_time == -1)
					continue;
				
                search_space n(nn);
                
                
                //if (((s.start_time + ex_time) <= n.p[i].left_capacity) && n.a[app_no] < apps[app_no].order.size() ) {
                if ( (s.start_time + ex_time <= c_time) && (n.a[app_no] < apps[app_no].order.size()) ) {
                    //cout<<"Node ("<<i<<") Left Capacity:"<<n.p[i].left_capacity<<endl;
                    //int temp_stime = s.start_time;
                    vector<sequence> t_seq;
                    bool olap=false;
                    int sc_time=s.start_time + c_time;
                    int initial_time = s.start_time;
                    //cout<<"It should have been:"<<sc_time<<endl;
                    for (int x=1; x<(lcm/c_time); x++) {
                        //int cache_time = temp_stime + x*c_time;
                        
                        int cache_time = initial_time + x*c_time;
                        //cout<<"Start Time Before:"<<s.start_time<<" "<<"Cache Time:"<<cache_time<<endl;
                        sequence s(app_no,nn.a[app_no]);
                        
                        s.start_time = check_overlap(m,apps,nn,i,j,app_no,ex_time,cache_time);
                        
                        //cout<<"Start Time After:"<<s.start_time<<" "<<"Cache Time:"<<cache_time<<endl;
                        if (s.start_time != cache_time) 
                            olap = true;
                        else
                            t_seq.push_back(s);
                        sc_time += c_time;
                    }
                    //cout<<"OLAP:"<<olap<<endl;
                    
                    if (!olap)
                    {
                        n.p[i].add_assignment_obj(s);
                        for (int x=0; x<t_seq.size(); x++)
                        { 
                            
                            n.p[i].add_assignment_obj(t_seq[x]);
                        }
                        
                        n.a[app_no] += 1;
                        n.est[app_no] = s.start_time + ex_time;
                        //cout<<"Nodes are getting pushed"<<endl;
                        q.push(n); 
                    }
                    
                }
                
			}
            
		}
        
        
	}
    
    
	return 0;
}
